Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights

摘要

Let $G$ be a graph and $\mathcal {S}$ be a subset of $Z$. A vertex-coloring$\mathcal {S}$-edge-weighting of $G$ is an assignment of weight $s$ by theelements of $\mathcal {S}$ to each edge of $G$ so that adjacent vertices havedifferent sums of incident edges weights. It was proved that every 3-connected bipartite graph admits a vertex-coloring$\{1,2\}$-edge-weighting (Lu, Yu and Zhang, (2011) \cite{LYZ}). In this paper,we show that the following result: if a 3-edge-connected bipartite graph $G$with minimum degree $\delta$ contains a vertex $u\in V(G)$ such that$d_G(u)=\delta$ and $G-u$ is connected, then $G$ admits a vertex-coloring$\mathcal {S}$-edge-weighting for $\mathcal {S}\in \{\{0,1\},\{1,2\}\}$. Inparticular, we show that every 2-connected and 3-edge-connected bipartite graphadmits a vertex-coloring $\mathcal {S}$-edge-weighting for $\mathcal {S}\in\{\{0,1\},\{1,2\}\}$. The bound is sharp, since there exists a family ofinfinite bipartite graphs which are 2-connected and do not admitvertex-coloring $\{1,2\}$-edge-weightings or vertex-coloring$\{0,1\}$-edge-weightings.